package day_7_4;

import java.util.ArrayList;
import java.util.List;

public class Main1 {
    /**
     * 99. 恢复二叉搜索树
     * https://leetcode.cn/problems/recover-binary-search-tree/description/
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    List<TreeNode> list = new ArrayList<>();

    public void recoverTree(TreeNode root) {
        dfs(root);
        TreeNode x = null;
        TreeNode y = null;
        for(int i = 0;i < list.size() - 1;i++) {
            if(list.get(i).val > list.get(i + 1).val) {
                y = list.get(i + 1);
                if(x == null) {
                    x = list.get(i);
                }
            }
        }

        // 替换x和y位置的val值
        if(x != null && y != null) {
            int tmp = x.val;
            x.val = y.val;
            y.val = tmp;
        }
    }

    public void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.left);
        list.add(root);
        dfs(root.right);
    }
}
